package features.advance.leetcode.string.medium;



import features.advance.leetcode.Solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 *
 * 提示：
 *
 * 1 <= n <= 8
 *
 * @author LIN
 * @date 2021-04-25
 */
public class Solution22 extends Solution {

    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    public static void main(String[] args) {
        // [
        // [1,1],
        // [2,2],
        // [3,5],
        // [4,15],
        // [5,]]
        int n = 1;
        Solution22 solution22 = new Solution22() {
            @Override
            public void a(int[] arr,int pos){
                if(arr != null && pos < arr.length){
                    System.out.println(arr[pos]);
                    a(arr,pos+1);
                }
            }
        };
        List<String> strings = solution22.generateParenthesis(n);
        System.out.println(strings);

        int[] a = {1,2,3,2,3,1,4,5,6,2,3};
        solution22.a(a,0);


    }


}
